package com.sort;

import java.util.Arrays;

/**
 * 基数排序演示
 *
 * @author Lvan
 */
public class RadixSort {
    public static void main(String[] args) {
        int[] arr = {63, 157, 189, 51, 101, 47, 141, 121, 157, 156,
                194, 117, 98, 139, 67, 133, 181, 12, 28, 0, 109};

        radixSort(arr);

        System.out.println(Arrays.toString(arr));
    }

    /**
     * LSD
     *
     * @param arr 待排序列，必须为自然数
     */
    private static void radixSort(int[] arr) {
        //待排序列最大值
        int max = arr[0];
        int exp;//指数

        //计算最大值
        for (int anArr : arr) {
            if (anArr > max) {
                max = anArr;
            }
        }

        //从个位开始，对数组进行排序
        for (exp = 1; max / exp > 0; exp *= 10) {
            //存储待排元素的临时数组
            int[] temp = new int[arr.length];
            //分桶个数
            int[] buckets = new int[10];

            //将数据出现的次数存储在buckets中
            for (int value : arr) {
                //(value / exp) % 10 :value的最底位(个位)
                buckets[(value / exp) % 10]++;
            }

            // 记录数据的位置
            for (int i = 1; i < 10; i++) {
                buckets[i] += buckets[i - 1];
            }

            //将数据存储到临时数组temp中
            // 一定要从后往前转
            /*
                (arr[i] / exp) % 10 是求出数字该位数上的数字
                buckets[(arr[i] / exp) % 10]找出该数字在桶里面的第几个数字
                buckets[(arr[i] / exp) % 10] - 1 转换为临时数组里面的坐标
                例如 数组[21,1,12,35,354,195,56,6,7,88]
                第一次排序
                0
                1 21 1
                2 12
                3
                4 354
                5 35 195
                6 56 6
                7 7
                8 88
                9
                第一次排序结果为：[21 1 12 354 35 195 56 6 7 88]

                第二次排序
                0 1 6 7
                1 12
                2 21
                3 35
                4
                5 354 56
                6
                7
                8 88
                9 195
                第二次排序结果为：[1 6 7 12 21 35 354 56 88 195]

                第三次排序                              计数  总计   临时数组坐标           结论：临时坐标数组下标 = 总计数 - 1
                0 1 6 7 12 21 35 56 88                 8    8     temp[7] ~ temp[0]
                1 195                                  1    9     temp[8]
                2
                3 354                                  1    10   temp[9]
                4
                5
                6
                7
                8
                9
                第三次排序结果为：[1 6 7 12 21 35 56 88 195 354]
             */
            for (int i = arr.length - 1; i >= 0; i--) {
                temp[buckets[(arr[i] / exp) % 10] - 1] = arr[i];
                buckets[(arr[i] / exp) % 10]--;
            }

            //将有序元素temp赋给arr
            System.arraycopy(temp, 0, arr, 0, arr.length);
        }

    }
}